import java.util.ArrayList;
/*
    Set的时间复杂度分析
    LinkedListSet   无序集合        最好的实现是基于哈希表HashSet
        add         原先链表的加只有O(1) 但是在集合中都要先contain一遍，所以是O(n) + O(1) 即O(n)
        contain     原先链表也是O(n)，所以这里也是O(n)
        delete      原先链表也是O(n)，所以这里也是O(n)

    BSTSet          有序集合        最好的实现是基于搜索树
   节点操作要么走左边要么走右边，则每递归一次都会排除几乎一半的元素，最多只会走这个树的高度次数完成操作
   所以三个操作全都是O(h)  h:高度
        add
        contain
        delete

    同样的数据可以构造成不同的二分搜索树，二分搜索树可能退化成链表
    例如:1 2 3 4 5 6
    如果从1当节点，那么就是形成一个右下的链表了，所以在最差情况BSTSet集合的时间复杂度为O(n)
    要解决这个问题就是构造平衡二叉树(后面学)

*/
public class Main {

    private static double testSet(Set<String> set, String filename){

        long startTime = System.nanoTime();

        System.out.println(filename);
        ArrayList<String> words = new ArrayList<>();
        if(FileOperation.readFile(filename, words)) {
            System.out.println("Total words: " + words.size());

            for (String word : words)
                set.add(word);
            System.out.println("Total different words: " + set.getSize());
        }
        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {

        String filename = "pride-and-prejudice.txt";

        BSTSet<String> bstSet = new BSTSet<>();
        double time1 = testSet(bstSet, filename);
        System.out.println("BST Set: " + time1 + " s");

        System.out.println();

        LinkedListSet<String> linkedListSet = new LinkedListSet<>();
        double time2 = testSet(linkedListSet, filename);
        System.out.println("Linked List Set: " + time2 + " s");

    }
}